import java.util.Stack;

/**
 * @author : zzr
 * @description :
 * @date :
 */

//排序均默认按照升序排列
public class Sort {

    /**
     * 直接插入排序方法
     *
     * 时间复杂度：
     *      最好情况：数据完全有序的时候 1 2 3 4 5 O(N)
     *      最坏情况：数据完全逆序的时候 5 4 3 2 1 O(N^2)
     * 结论：当所给的数据 有序程度越高 则该方法的排序速度越快
     * 场景：现在有一组基本有序的数据，那么你用那个排序好一些？
     *
     * 空间复杂度：O(1)
     * 稳定性：稳定
     *
     *      一个本身就是稳定的排序，是可以实现为不稳定的
     *      但一个本身就不稳定的排序 是不可能实现为稳定的排序的
     * @param array
     */
    public static void insertSort(int[] array) {

        if(null == array || 0 == array.length)
            return;

        for (int i = 1; i < array.length; i++) {

            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    /**
     * 希尔排序
     * 按照Knuth的理论，其时间复杂度大致为 n^1.3 ~ n^1.5
     * 空间复杂度为： O(1)
     *
     * 稳定性：不稳定的排序
     * @param array
     */
    public static void shellSort(int[] array) {
        int gap = array.length;

        while(gap > 1) {
            gap /= 2;
            shell(array, gap);
        }
    }

    private static void shell(int[] array, int gap) {

        if(null == array || 0 == array.length)
            return;

        for (int i = gap; i < array.length; i += gap) {
            int tmp = array[i];
            int j = i - gap;
            for(; j >= 0; j -= gap) {
                if(array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    /**
     * 选择排序
     *      时间复杂度： 没有最好和最坏情况 都是O(N^2)
     *      空间复杂度：O(1)
     *      稳定性：不稳定的排序
     * @param array
     */
    public static void selectSort(int[] array) {

        if(null == array || 0 == array.length)
            return;

        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, minIndex, i);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 选择排序的改良版
     * @param array
     */
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right ; i++) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,left, minIndex);
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

    /**
     * 堆排序：
     *      时间复杂度：O(n * logN)
     *      空间复杂度：O(1)
     *      稳定性：不稳定
     *
     *      数据量非常大的时候 堆排序 一定 比 希尔排序快
     * @param array
     */
    public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array,0, end);
            shiftDown(array,0,end);
            end--;
        }
    }

    private static void createBigHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0 ; parent--) {
            shiftDown(array, parent, array.length);
        }
    }

    private static void shiftDown(int[] array, int parent, int end) {
        int child = 2 * parent + 1;
        while(child < end) {
            if(child + 1 < end && array[child] < array[child + 1]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    /**
     * 冒泡排序;
     *      时间复杂度： O(N^2)
     *      优化flg后，最好的情况O(N)
     *      空间复杂度：O(1)
     *      稳定性：稳定的排序
     * @param array
     */
    public static void bubbkeSort(int[] array) {
        //比较的趟数
        for (int i = 0; i < array.length; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                //每一轮的比较
                if(array[j] > array[j + 1]) {
                    swap(array,j , j + 1);
                    flg = true;
                }
            }
            if(false == flg) {
                return;
            }
        }
    }

    /**
     * 快速排序
     * 时间复杂度：
     *      最好情况：O(N * logN) 满二叉树 / 完全二叉树
     *      最坏情况：O(N ^ 2) 单分支树
     *
     * 空间复杂度：
     *      最好情况：O(logN) 满二叉树
     *      最坏情况：O(N) 单分支树
     * @param array
     */
    public static void quickSort1(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int start, int end) {
        //左右边只有一个结点 或者 一个结点也没有
        if(start >= end) {
            return;
        }

        if(end - start + 1 <= 15) {
            insertSortRange(array, start, end);
            return;
        }
        //三数取中法
        int index = midOfThree(array, start, end); //得到中间值的下标

        swap(array,start,index); //交换完成之后，保证start下标索引的值是中间大小的值

        int pivot = partition2(array, start, end);
        quick(array,start,pivot - 1);
        quick(array,pivot + 1, end);
    }

    /**
     * 区间进行快速排序
     * @param array
     * @param begin
     * @param end
     */
    private static void insertSortRange(int[] array, int begin, int end) {
        for (int i = begin + 1; i <= end ; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= begin; j--) {
                if(array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    /**
     * 适用于Heare法的基准值法
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] array, int left, int right) {
        int key = array[left];
        int i = left;
        while(left < right) {
            while(left < right && array[right] >= key) {
                right--;
            }
            //当走完上面两行代码后，right一定是比key值大的元素的索引
            while(left < right && array[left] <= key) {
                left++;
            }
            //当走完上面的两行代码后，left一定是比key值小的元素的索引
            //对饮的元素交换位置
            swap(array,left,right);
        }
        swap(array, left, i);
        return left;
    }

    private static int partition2(int[] array, int left, int right) {

        //用key挖第一个坑
        int key = array[left];

        while (left < right) {
            while(left < right && array[right] >= key) {
                right--;
            }
            //right指向的下标索引 一定是比key小的数据
            //right找到数据后，用该数据填坑
            array[left] = array[right];
            //但是上面这行代码在填坑的同时 也 创建了新的坑

            while (left < right && array[left] <= key) {
                left++;
            }
            //left指向的下标索引 一定是比key大的数据
            //left指向的下标索引再来填刚刚right所挖的坑
            array[right] = array[left];
        }

        //循环结束 left和right相遇
        //把最开始挖坑的数据填回最后一个坑
        array[left] = key;

        return left;
    }

    /**
     * 前后指针法
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition3(int[] array, int left, int right) {
        int prev = left;
        int cur = prev + 1;
        while(cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, cur, prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }

    private static int midOfThree(int[] array, int left, int right) {
        int mid = (left + right) / 2;
        if(array[left] < array[right]) { //left 小于 right
            if(array[mid] < array[left]) { // mid 小于 left
                return left;  //left为中间值
            } else if(array[mid] > array[right]) { //mid 大于 right
                return right;  //right为中间值
            } else { //mid为中间值
                return mid;
            }
        } else { //left 大于等于 right
            if(array[mid] > array[left]) { //mid 大于 left
                return left; //left为中间值
            } if(array[mid] < array[right]) { //mid 小于 right
                return right; //right 为中间值
            } else {
                return mid; //mid 为中间值
            }
        }
    }


    public static void quickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        int piovt = partition(array,left,right);
        if(piovt - 1 > left) {
            //先压入左 再 压入右
            stack.push(left);
            stack.push(piovt - 1);
        }
        if(piovt + 1 < right) {
            stack.push(piovt + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            piovt = partition(array,left,right);
            if(piovt - 1 > left) {
                stack.push(left);
                stack.push(piovt - 1);
            }
            if(piovt + 1 < right) {
                stack.push(piovt + 1);
                stack.push(right);
            }
        }
    }

    /**
     * 归并排序
     * 时间复杂度：O(N * logN)
     * 空间复杂度：O(N)
     * 稳定的排序
     * 插入 冒泡 归并排序是稳定的排序
     * @param array
     */
    public static void mergeSort(int[] array) {
        mergeSortFunc(array, 0, array.length - 1);
    }

    private static void mergeSortFunc(int[] array, int left, int right) {
       //递归结束的条件：
        if(left >= right) 
            return;
        int mid = (left + right) / 2;
        
        //递归
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid + 1,right);
        
        //合并
        merge(array,left,right,mid);
        
    }

    private static void merge(int[] array, int left, int right, int mid) {
        int s1 = left;
        int s2 = mid + 1;
        int[] tmpArr = new int[right - left + 1];
        int k = 0;
        //s1和s2是为了证明两个区间都是有数据的
        while(s1 <= mid && s2 <= right) {
            if(array[s2] <= array[s1]) {
                tmpArr[k] = array[s2];
                k++;
                s2++;
            } else {
                tmpArr[k] = array[s1];
                k++;
                s1++;
            }
        }

        //代码执行到现在，证明有一个序列段为空了
        while (s1 <= mid) {
            tmpArr[k] = array[s1];
            k++;
            s1++;
        }

        while(s2 <= right) {
            tmpArr[k] = array[s2];
            k++;
            s2++;
        }

        //tmpArr 里面一定是这个区间内有序的数据了
        //再将这个tmpArr 临时数组合并回之前的数组
        //注意，这里不能直接array[i] = tmpArr[i]
        //如果在合并右边的数据的时候，右边的数据的索引在原来数组的索引并不是从0开始
        //可以加left进行向后推移
        for (int i = 0; i < tmpArr.length; i++) {
            array[i + left] = tmpArr[i];
        }
    }

    /**
     * 归并排序的非递归实现
     * @param array
     */
    public static void mergeSortNor(int[] array) {

        int gap = 1;

        while (gap < array.length) {
            for (int i = 0; i < array.length; i += 2 * gap) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;

                if(mid >= array.length) {
                    mid = array.length - 1;
                }
                if(right >= array.length) {
                    right = array.length - 1;
                }
                merge(array,left,right,mid);
            }
            gap *= 2;
        }
    }


    /**
     * 计数排序
     *      时间复杂度：O(N + 序列段的范围大小)
     *      空间复杂度：O(序列段的范围大小)
     *
     *      稳定性：下面的代码中 是不稳定的，但计数排序是稳定的，需要其他的方法
     *      在下面方法的状态下进行改进，此处不作介绍，认定计数排序为稳定的
     * @param array
     */
    public static void countSort(int[] array) {
        int minVal = array[0];
        int maxVal = array[0];

        //找到序列段中值最大和最小的元素
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxVal) {
                maxVal = array[i];
            }

            if(array[i] < minVal) {
                minVal = array[i];
            }
        }

        int[] countArr = new int[maxVal - minVal + 1];

        //遍历原数组，统计每个元素出现的次数
        for (int i = 0; i < array.length; i++) {
            int count = array[i];
            //统计每个元素出现的次数的关键代码
            countArr[count - minVal]++;
        }

        //遍历countArr数组 把元素写回array
        int index = 0;//重新表示array数组的下标
        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i] > 0) {
                array[index] = i + minVal;
                index++;
                countArr[i]--;
            }
        }
    }
}

